/**
 * 1. 两数之和
 * https://leetcode-cn.com/problems/two-sum/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {number[]} nums
 * @param {number[]} indexes
 * @param {number} length
 * @param {number} target
 * @return {number}
 */
function exist(nums, indexes, length, target) {
  let left = 0;
  let right = length - 1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    if (nums[indexes[middle]] === target) {
      return indexes[middle];
    }
    if (nums[indexes[middle]] > target) {
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return -1;
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  const indexes = new Array(nums.length).fill(0);
  for (let i = 1; i < nums.length; i += 1) {
    indexes[i] = i;
  }
  indexes.sort((a, b) => (nums[a] >= nums[b] ? 1 : -1));
  for (let i = indexes.length - 1; i >= 1; i -= 1) {
    const part = target - nums[indexes[i]];
    const partIndex = exist(nums, indexes, i, part);
    if (partIndex >= 0) {
      return [partIndex, indexes[i]];
    }
  }
  return [];
}

console.log(displayBaseArray(twoSum([2, 7, 11, 15], 9)) === '[0,1]');
console.log(displayBaseArray(twoSum([3, 2, 4], 6)) === '[1,2]');
console.log(displayBaseArray(twoSum([3, 3], 6)) === '[0,1]');
